| 翻訳と辞書 |
| Hirsch conjecture ： ウィキペディア英語版 |
Hirsch conjecture
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an ''n''-facet polytope in ''d''-dimensional Euclidean space has diameter no more than ''n'' − ''d''. That is, any two vertices of the polytope must be connected to each other by a path of length at most ''n'' − ''d''. The conjecture was first put forth in a letter by to George B. Dantzig in 1957〔〔, pp. 160 and 168.〕 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general.
The Hirsch conjecture was proven for ''d'' < 4 and for various special cases,〔E.g. see for 0-1 polytopes.〕 while the best known upper bounds on the diameter are only sub-exponential in ''n'' and ''d''.〔.〕 After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos Leal, from the University of Cantabria.〔.〕〔.〕 The result was presented at the conference ''100 Years in Seattle: the mathematics of Klee and Grünbaum'' and appeared in ''Annals of Mathematics''. Specifically, the paper presented a 43-dimensional polytope of 86 facets with a diameter of more than 43. The counterexample has no direct consequences for the analysis of the simplex method, as it does not rule out the possibility of a larger but still linear or polynomial number of steps.
Various equivalent formulations of the problem had been given, such as the ''d''-step conjecture, which states that the diameter of any 2''d''-facet polytope in ''d''-dimensional Euclidean space is no more than ''d''.〔, p. 84.〕〔.〕
==Notes==
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Hirsch conjecture」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|